// addrspace.cc 
//	Routines to manage address spaces (executing user programs).
//
//	In order to run a user program, you must:
//
//	1. link with the -N -T 0 option 
//	2. run coff2noff to convert the object file to Nachos format
//		(Nachos object code format is essentially just a simpler
//		version of the UNIX executable object code format)
//	3. load the NOFF file into the Nachos file system
//		(if you haven't implemented the file system yet, you
//		don't need to do this last step)
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "system.h"
#include "addrspace.h"
#include "noff.h"
#ifdef HOST_SPARC
#include <strings.h>
#endif

//----------------------------------------------------------------------
// SwapHeader
// 	Do little endian to big endian conversion on the bytes in the 
//	object file header, in case the file was generated on a little
//	endian machine, and we're now running on a big endian machine.
//----------------------------------------------------------------------


static void 
SwapHeader (NoffHeader *noffH)
{
	noffH->noffMagic = WordToHost(noffH->noffMagic);
	noffH->code.size = WordToHost(noffH->code.size);
	noffH->code.virtualAddr = WordToHost(noffH->code.virtualAddr);
	noffH->code.inFileAddr = WordToHost(noffH->code.inFileAddr);
	noffH->initData.size = WordToHost(noffH->initData.size);
	noffH->initData.virtualAddr = WordToHost(noffH->initData.virtualAddr);
	noffH->initData.inFileAddr = WordToHost(noffH->initData.inFileAddr);
	noffH->uninitData.size = WordToHost(noffH->uninitData.size);
	noffH->uninitData.virtualAddr = WordToHost(noffH->uninitData.virtualAddr);
	noffH->uninitData.inFileAddr = WordToHost(noffH->uninitData.inFileAddr);
}

//----------------------------------------------------------------------
// AddrSpace::AddrSpace
// 	Create an address space to run a user program.
//	Load the program from a file "executable", and set everything
//	up so that we can start executing user instructions.
//
//	Assumes that the object code file is in NOFF format.
//
//	First, set up the translation from program memory to physical 
//	memory.  For now, this is really simple (1:1), since we are
//	only uniprogramming, and we have a single unsegmented page table
//
//	"executable" is the file containing the object code to load into memory
//----------------------------------------------------------------------

// Bitmap only looks within a page 
//	to look at the next page mark the (pageNumber*pageSize) bit
// and look for continuous pages


AddrSpace::AddrSpace(OpenFile *executable)
{
//	printf("IN ADDRESS SPACE\n");
	OpenFile *MYexecutable = executable;
	if(currentThread->getParent() != NULL){
//		printf("currentThread: %d parent is: %d\n", currentThread->getID(), currentThread->getParent()->getID());
	}
	DEBUG('t', "IN ADDRESS SPACE\n");
    NoffHeader noffH;
    unsigned int i, size;
	
	int firstPage;
	int prevPage;
	int nextPage;
	int tempAddress;
	int sizeCount = 0;
	isFree = true;

    executable->ReadAt((char *)&noffH, sizeof(noffH), 0); 
	
    if ((noffH.noffMagic != NOFFMAGIC) && 
		(WordToHost(noffH.noffMagic) == NOFFMAGIC))
    	SwapHeader(&noffH);
    ASSERT(noffH.noffMagic == NOFFMAGIC);

// how big is address space?
    size = noffH.code.size + noffH.initData.size + noffH.uninitData.size 
			+ UserStackSize;	// we need to increase the size
									// to leave room for the stack
									
    numPages = divRoundUp(size, PageSize);
    size = numPages * PageSize;
	
	DEBUG('t', "Checking Bitmap\n");
	
	firstPage = myBitMap->Find();
	prevPage = firstPage - 1;
	myBitMap->Clear(firstPage);
	
	int currPage = 0;									// counter for how many bits you went through until you hit max
	int contigAdds = 0;									// number of contiguous addresses

//	int makePages = 1;
	
	// variables for best fit and worst fit
	
	int bestFirstAddress;
	
	int previousSize;
	int currentSize = 0;
	
	bool didFirstCheck = false;
	bool foundEnough = false;
	
//	int calvinBerry;
	
//	if(machine->ReadRegister(2) == 2){
//		DEBUG('t', "It is 2\n");
//		scanf("%d", &calvinBerry);
//	}
	
if(myFlag == 1){	// FIRST FIT
	while(contigAdds < numPages){						// while you dont have enough space
		if(myBitMap->Test(currPage) == false){			
			nextPage = currPage;					
			if(nextPage != prevPage+1){					// check if the pages are contiguous
				contigAdds = 0;
				firstPage = currPage;					// firstPage = the page you currently have
			}
			prevPage = nextPage;						// set preveious page to the current one
			contigAdds++;
		}	// end of if 
		currPage++;
		if(currPage == NumPhysPages){					// there is not enough space to run the prog
			isFree = false;
			break;
		}	// end of if currPage == NumPhysPages
	}	// end of while
}

if(myFlag == 2){	// BEST FIT
	bestFirstAddress = firstPage;
	while(currPage < NumPhysPages){						// while you dont have enough space
		if(myBitMap->Test(currPage) == false){			
			nextPage = currPage;					
			if(nextPage != prevPage+1){					// check if the pages are contiguous	
				if(didFirstCheck == true && contigAdds >= numPages){	// already found non contiguous code
					if(previousSize > currentSize)						// if the previousSize is greater than the currentSize then 
						bestFirstAddress = firstPage;					// replace the current best Address with this ones
				}
				if(didFirstCheck == false && contigAdds >= numPages){	// first time it not being contiguous save the first page only if
					didFirstCheck = true;								// the memory has enough space
					bestFirstAddress = firstPage;
					previousSize = currentSize;
				}
				firstPage = currPage;					// firstPage = the page you currently have
				currentSize = 0;
				contigAdds = 0;
			}
			prevPage = nextPage;						// set preveious page to the current one
			contigAdds++;
			if(contigAdds >= numPages && foundEnough == false){	// there was enough contiguous adds for the program to fit in the mem
				foundEnough = true;
			}
		}	// end of if 
		currPage++;
		currentSize++;
		if(currPage == NumPhysPages && foundEnough == false){		// you got to the end and u never found enough space
			isFree = false;
			break;
		}	// end of if currPage == NumPhysPages
	}	// end of while
	firstPage = bestFirstAddress;
}

if(myFlag == 3){	// WORST FIT
	bestFirstAddress = firstPage;
	while(currPage < NumPhysPages){						// while you dont have enough space
		if(myBitMap->Test(currPage) == false){			
			nextPage = currPage;					
			if(nextPage != prevPage+1){					// check if the pages are contiguous	
				if(didFirstCheck == true && contigAdds >= numPages){	// already found non contiguous code
					if(previousSize < currentSize)						// if the previousSize is greater than the currentSize then 
						bestFirstAddress = firstPage;					// replace the current best Address with this ones
				}
				if(didFirstCheck == false && contigAdds >= numPages){	// first time it not being contiguous save the first page only if
					didFirstCheck = true;								// the memory has enough space
					bestFirstAddress = firstPage;
					previousSize = currentSize;
				}
				firstPage = currPage;					// firstPage = the page you currently have
				currentSize = 0;
				contigAdds = 0;
			}
			prevPage = nextPage;						// set preveious page to the current one
			contigAdds++;
			if(contigAdds >= numPages && foundEnough == false){	// there was enough contiguous adds for the program to fit in the mem
				foundEnough = true;
			}
		}	// end of if 
		currPage++;
		currentSize++;
		if(currPage == NumPhysPages && foundEnough == false){		// you got to the end and u never found enough space
			isFree = false;
			break;
		}	// end of if currPage == NumPhysPages
	}	// end of while
	firstPage = bestFirstAddress;
}

else{ // defaults to FIRST FIT
	while(contigAdds < numPages){						// while you dont have enough space
		if(myBitMap->Test(currPage) == false){			
			nextPage = currPage;					
			if(nextPage != prevPage+1){					// check if the pages are contiguous
				contigAdds = 0;
				firstPage = currPage;					// firstPage = the page you currently have
			}
			prevPage = nextPage;						// set preveious page to the current one
			contigAdds++;
		}	// end of if 
		currPage++;
		if(currPage == NumPhysPages){					// there is not enough space to run the prog
			isFree = false;
			break;
		}	// end of if currPage == NumPhysPages
	}	// end of while
	
}	// end of switch

	DEBUG('t', "contig adds %d\n", contigAdds);
	
	if(isFree == false){								// there was not enough memory for the program
		printf("Not enough space available!\n");
		//currentThread->Finish(); //**********************************************
	}
	if(noffH.code.size == 0){							// if the size of it is 0
		printf("There is nothing to run\n");
		//currentThread->Finish();  //**********************************************
	}
	
	// ***********NEED TO CLEAR ALL OF THE BITS WE SEARCHED******
	if(isFree == true){
	DEBUG('t', "DID CHECK\n");
	
	// change or get rid of next line ------------------------------------------------------------
    ASSERT(numPages <= NumPhysPages);		// check we're not trying
						// to run anything too big --
						// at least until we have
						// virtual memory

    DEBUG('a', "Initializing address space, num pages %d, size %d\n", 
					numPages, size);

	// first, set up the translation 
	DEBUG('t', "DOING PAGE\n");
	specialFirstPage = firstPage;					//	for the cleanup later on
	sizeOfEx = size;								//
	
	
    pageTable = new TranslationEntry[numPages]; // change or delete line
	if(isFree == true){
	//	printf("\npageTable: ");
	}
	
	for (i = 0; i < numPages; i++) {
		// change or delete next line -----------------------------------------------------------------
		pageTable[i].virtualPage = i;							// for now, virtual page # = phys page #
		DEBUG('t', "virt PAGE %d\n", pageTable[i].virtualPage);
		pageTable[i].physicalPage = firstPage+i;		// the first address for the memory, set above
		DEBUG('t', "phys PAGE %d\n", pageTable[i].physicalPage);
		if(isFree == true){
		//	printf("%d, ", pageTable[i].physicalPage);
			myBitMap->Mark(firstPage+i); 	//*****double check this
		}
		pageTable[i].valid = TRUE;
		pageTable[i].use = FALSE;
		pageTable[i].dirty = FALSE;
		pageTable[i].readOnly = FALSE;  // if the code segment was entirely on 
						// a separate page, we could set its 
						// pages to be read-only
    }
//	printf("\n");
	int numShouts;
    
if(isFree == true){
	for(int x = 0; x < NumPhysPages; x++){
		if(myBitMap->Test(x) == true){
		//	printf("%d", 1);
		}
		if(myBitMap->Test(x) == false){
		//	printf("%d", 0);
		}
	}
//	printf("\n\n\n");
}
//	scanf("%d", &numShouts);
	// zero out the entire address space, to zero the unitialized data segment 
	// and the stack segment

	DEBUG('t', "ZEROING OUT\n");

	int tempADDRESS;
	tempADDRESS = firstPage*PageSize;
	
	
	// clear the block of memory found for the program
	memset(&(machine->mainMemory[tempADDRESS]), 0, size);
		
	DEBUG('t', "After 0 out\n");
	


	// then, copy in the code and data segments into memory
    if (noffH.code.size > 0) {
		DEBUG('t', "1\n");
        
		DEBUG('a', "Initializing code segment, at 0x%x, size %d\n", 
			noffH.code.virtualAddr, noffH.code.size);
					
		DEBUG('t', "Size of code %d\n", noffH.code.size);
		DEBUG('t', "InFileAddress %d\n", noffH.code.inFileAddr);
		DEBUG('t', "First address of cont. block %d\n", firstPage);
		DEBUG('t', "Last address of cont. block %d\n", prevPage);
		DEBUG('t', "Size of executable %d\n", size);
		DEBUG('t', "tempADDRESS %d\n", tempADDRESS);
		
		if(executable == NULL){
			DEBUG('t', "lol its definetly null\n");
		}
		
		executable->ReadAt(&(machine->mainMemory[noffH.code.virtualAddr + tempADDRESS]), // change or delete
			noffH.code.size, noffH.code.inFileAddr);
		
		DEBUG('t', "did it\n");
    }
    if (noffH.initData.size > 0) {
	DEBUG('t', "2\n");
        DEBUG('a', "Initializing data segment, at 0x%x, size %d\n", 
			noffH.initData.virtualAddr, noffH.initData.size);
        executable->ReadAt(&(machine->mainMemory[noffH.initData.virtualAddr + tempADDRESS]), // change or delete
			noffH.initData.size, noffH.initData.inFileAddr);
			
    }
DEBUG('t', "did nachos\n");
}
}//

//----------------------------------------------------------------------
// AddrSpace::~AddrSpace
// 	Dealloate an address space.  Nothing for now!
//----------------------------------------------------------------------

AddrSpace::~AddrSpace()
{
	delete pageTable;
}


bool AddrSpace::hadEnoughSpace(){
	return isFree;
}

int AddrSpace::getFirstPage(){
	return specialFirstPage;
}

int AddrSpace::getNumPages(){
	return numPages;
}

void AddrSpace::RemoveTheMem(){
	interrupt->SetLevel(IntOff);
//	printf("CLEARING MEM FOR THREAD %s\n", currentThread->getName());
	//printf("CLEARING : ");
	for(int i = 0; i < currentThread->space->getNumPages(); i++){		//special first page
	//	printf("%d, ", currentThread->space->getFirstPage()+i);
		myBitMap->Clear(currentThread->space->getFirstPage()+i);						// clear it from bitmap
	}
	printf("\n");
	interrupt->SetLevel(IntOn);
}


//----------------------------------------------------------------------
// AddrSpace::InitRegisters
// 	Set the initial values for the user-level register set.
//
// 	We write these directly into the "machine" registers, so
//	that we can immediately jump to user code.  Note that these
//	will be saved/restored into the currentThread->userRegisters
//	when this thread is context switched out.
//--------------------------------------------------NACHOS--------------------

void
AddrSpace::InitRegisters()
{
    int i;

    for (i = 0; i < NumTotalRegs; i++)
	machine->WriteRegister(i, 0);

    // Initial program counter -- must be location of "Start"
    machine->WriteRegister(PCReg, 0);	

    // Need to also tell MIPS where next instruction is, because
    // of branch delay possibility
    machine->WriteRegister(NextPCReg, 4);

   // Set the stack register to the end of the address space, where we
   // allocated the stack; but subtract off a bit, to make sure we don't
   // accidentally reference off the end!
    machine->WriteRegister(StackReg, numPages * PageSize - 16);
    DEBUG('a', "Initializing stack register to %d\n", numPages * PageSize - 16);
}

//----------------------------------------------------------------------
// AddrSpace::SaveState
// 	On a context switch, save any machine state, specific
//	to this address space, that needs saving.
//
//	For now, nothing!
//----------------------------------------------------------------------

void AddrSpace::SaveState() 
{}

//----------------------------------------------------------------------
// AddrSpace::RestoreState
// 	On a context switch, restore the machine state so that
//	this address space can run.
//
//      For now, tell the machine where to find the page table.
//----------------------------------------------------------------------

void AddrSpace::RestoreState() 
{
    machine->pageTable = pageTable;
    machine->pageTableSize = numPages;
}



/*  						INITIAL ADDRESS SPACE
// addrspace.cc 
//	Routines to manage address spaces (executing user programs).
//
//	In order to run a user program, you must:
//
//	1. link with the -N -T 0 option 
//	2. run coff2noff to convert the object file to Nachos format
//		(Nachos object code format is essentially just a simpler
//		version of the UNIX executable object code format)
//	3. load the NOFF file into the Nachos file system
//		(if you haven't implemented the file system yet, you
//		don't need to do this last step)
//
// Copyright (c) 1992-1993 The Regents of the University of California.
// All rights reserved.  See copyright.h for copyright notice and limitation 
// of liability and disclaimer of warranty provisions.

#include "copyright.h"
#include "system.h"
#include "addrspace.h"
#include "noff.h"
#ifdef HOST_SPARC
#include <strings.h>
#endif

//----------------------------------------------------------------------
// SwapHeader
// 	Do little endian to big endian conversion on the bytes in the 
//	object file header, in case the file was generated on a little
//	endian machine, and we're now running on a big endian machine.
//----------------------------------------------------------------------

static void 
SwapHeader (NoffHeader *noffH)
{
	noffH->noffMagic = WordToHost(noffH->noffMagic);
	noffH->code.size = WordToHost(noffH->code.size);
	noffH->code.virtualAddr = WordToHost(noffH->code.virtualAddr);
	noffH->code.inFileAddr = WordToHost(noffH->code.inFileAddr);
	noffH->initData.size = WordToHost(noffH->initData.size);
	noffH->initData.virtualAddr = WordToHost(noffH->initData.virtualAddr);
	noffH->initData.inFileAddr = WordToHost(noffH->initData.inFileAddr);
	noffH->uninitData.size = WordToHost(noffH->uninitData.size);
	noffH->uninitData.virtualAddr = WordToHost(noffH->uninitData.virtualAddr);
	noffH->uninitData.inFileAddr = WordToHost(noffH->uninitData.inFileAddr);
}

//----------------------------------------------------------------------
// AddrSpace::AddrSpace
// 	Create an address space to run a user program.
//	Load the program from a file "executable", and set everything
//	up so that we can start executing user instructions.
//
//	Assumes that the object code file is in NOFF format.
//
//	First, set up the translation from program memory to physical 
//	memory.  For now, this is really simple (1:1), since we are
//	only uniprogramming, and we have a single unsegmented page table
//
//	"executable" is the file containing the object code to load into memory
//----------------------------------------------------------------------

AddrSpace::AddrSpace(OpenFile *executable)
{
    NoffHeader noffH;
    unsigned int i, size;

    executable->ReadAt((char *)&noffH, sizeof(noffH), 0);
    if ((noffH.noffMagic != NOFFMAGIC) && 
		(WordToHost(noffH.noffMagic) == NOFFMAGIC))
    	SwapHeader(&noffH);
    ASSERT(noffH.noffMagic == NOFFMAGIC);

// how big is address space?
    size = noffH.code.size + noffH.initData.size + noffH.uninitData.size 
			+ UserStackSize;	// we need to increase the size
						// to leave room for the stack
    numPages = divRoundUp(size, PageSize);
    size = numPages * PageSize;

    ASSERT(numPages <= NumPhysPages);		// check we're not trying
						// to run anything too big --
						// at least until we have
						// virtual memory

    DEBUG('a', "Initializing address space, num pages %d, size %d\n", 
					numPages, size);
// first, set up the translation 
    pageTable = new TranslationEntry[numPages];
    for (i = 0; i < numPages; i++) {
	pageTable[i].virtualPage = i;	// for now, virtual page # = phys page #
	pageTable[i].physicalPage = i;
	pageTable[i].valid = TRUE;
	pageTable[i].use = FALSE;
	pageTable[i].dirty = FALSE;
	pageTable[i].readOnly = FALSE;  // if the code segment was entirely on 
					// a separate page, we could set its 
					// pages to be read-only
    }
    
// zero out the entire address space, to zero the unitialized data segment 
// and the stack segment
    bzero(machine->mainMemory, size);

// then, copy in the code and data segments into memory
    if (noffH.code.size > 0) {
        DEBUG('a', "Initializing code segment, at 0x%x, size %d\n", 
			noffH.code.virtualAddr, noffH.code.size);
        executable->ReadAt(&(machine->mainMemory[noffH.code.virtualAddr]),
			noffH.code.size, noffH.code.inFileAddr);
    }
    if (noffH.initData.size > 0) {
        DEBUG('a', "Initializing data segment, at 0x%x, size %d\n", 
			noffH.initData.virtualAddr, noffH.initData.size);
        executable->ReadAt(&(machine->mainMemory[noffH.initData.virtualAddr]),
			noffH.initData.size, noffH.initData.inFileAddr);
    }

}

//----------------------------------------------------------------------
// AddrSpace::~AddrSpace
// 	Dealloate an address space.  Nothing for now!
//----------------------------------------------------------------------

AddrSpace::~AddrSpace()
{
   delete pageTable;
}

//----------------------------------------------------------------------
// AddrSpace::InitRegisters
// 	Set the initial values for the user-level register set.
//
// 	We write these directly into the "machine" registers, so
//	that we can immediately jump to user code.  Note that these
//	will be saved/restored into the currentThread->userRegisters
//	when this thread is context switched out.
//----------------------------------------------------------------------

void
AddrSpace::InitRegisters()
{
    int i;

    for (i = 0; i < NumTotalRegs; i++)
	machine->WriteRegister(i, 0);

    // Initial program counter -- must be location of "Start"
    machine->WriteRegister(PCReg, 0);	

    // Need to also tell MIPS where next instruction is, because
    // of branch delay possibility
    machine->WriteRegister(NextPCReg, 4);

   // Set the stack register to the end of the address space, where we
   // allocated the stack; but subtract off a bit, to make sure we don't
   // accidentally reference off the end!
    machine->WriteRegister(StackReg, numPages * PageSize - 16);
    DEBUG('a', "Initializing stack register to %d\n", numPages * PageSize - 16);
}

//----------------------------------------------------------------------
// AddrSpace::SaveState
// 	On a context switch, save any machine state, specific
//	to this address space, that needs saving.
//
//	For now, nothing!
//----------------------------------------------------------------------

void AddrSpace::SaveState() 
{}

//----------------------------------------------------------------------
// AddrSpace::RestoreState
// 	On a context switch, restore the machine state so that
//	this address space can run.
//
//      For now, tell the machine where to find the page table.
//----------------------------------------------------------------------

void AddrSpace::RestoreState() 
{
    machine->pageTable = pageTable;
    machine->pageTableSize = numPages;
}
*/